package my.jwds.p229;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MajorityElement {

    public static void main(String[] args) {
        MajorityElement obj = new MajorityElement();
    }

    public List<Integer> majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        int n = nums.length/3;
        for (int num : nums) {
            Integer count = map.get(num);
            if (count == null){
                count = 0;
            }
            if (count != -1){
                if (++count > n){
                    count = -1;
                    res.add(num);
                }
                map.put(num,count);
            }
        }
        return res;
    }

    /**
     * 摩尔投票法
     * @param nums
     * @return
     */
    public List<Integer> majorityElement_1(int[] nums) {
        int num1 = 0,num2=0,num1Count =0,num2Count =0;
        for (int num : nums) {
            if (num1 == num){
                num1Count++;
            }else if (num2 == num){
                num2Count++;
            }else if (num1Count == 0){
                num1 = num;
                num1Count++;
            }else if (num2Count == 0){
                num2 = num;
                num2Count++;
            }else{
                num1Count --;
                num2Count --;
            }
        }
        num1Count = 0;
        num2Count = 0;
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if (num1 == num){
                num1Count++;
            }else if (num2 == num){
                num2Count++;
            }
        }
        if (num1Count > nums.length/3){
            res.add(num1);
        }
        if (num2Count > nums.length/3){
            res.add(num2);
        }
        return res;
    }
}